package Tree_09.ThreadedBinaryTree_03;

/*
 * @Author 罗
 * @date 2020/3/21 - 1:06 下午
 *
 */

import Tree_09.BinaryTree_01.DataStructure.BinaryTree;

import Tree_09.BinaryTree_01.DataStructure.Node;
import Tree_09.BinaryTree_01.Entity.HeroNode;

/**
 * 线索二叉树基本介绍
 *
 * n个结点的二叉链表中含有n+1  【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，
 * 存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
 *
 * 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。
 * 根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
 *
 * 一个结点的前一个结点，称为前驱结点
 * 一个结点的后一个结点，称为后继结点
 */
public class ThreadedBinaryTree extends BinaryTree {
    /*
     * 为节点添加了线索化特性
     * 说明: 当线索化二叉树后，Node节点的 属性 left 和 right ，有如下情况:
     *   left 指向的是左子树，也可能是指向的前驱节点
     *   right指向的是右子树，也可能是指向后继节点
     */
    private ThreadedNode root;

    /*
     * 普通二叉树中，子节点不能找到父节点（顺序二叉树可以用公式找到）
     *      为了能找到父节点，需要有一个指针
     * 为了实现前驱节点的线索化，需要创建指向当前节点的前驱节点的指针
     * 在进行地柜线索化的时候，prePointer总是保留前一个节点
     *      不用给每个节点都添加前驱指针，在线索化二叉树里添加就行了
     * */
    ThreadedNode prePointer;

    /**
     * 遍历线索化的二叉树，只针对前序二叉树
     */
    public void threadedList() {
        ThreadedNode temp = root;
        if (temp == null) {
            System.out.println("二叉树为null，遍历失败");
            return;
        }
        while (temp != null) {
            /*
             * 找到线索化之后的第一个节点
             * */
            while (temp.leftPointerType == null) {
                temp = (ThreadedNode) (temp.left);
            }
            /*
             * 当right为后继节点的时候就一直遍历
             * */
            while (temp.rightPointerType == RightPointerType.descendantNode) {
                System.out.println(temp.item);
                temp = (ThreadedNode) (temp.right);
            }
            /*
             * 如果 right 指向下一个节点不是后继节点
             * 那他指向的就是右子树
             * */
            System.out.println(temp.item);
            temp = (ThreadedNode) (temp.right);
        }
    }

    /**
     * 遍历后序线索化的二叉树
     */
    public void threadedListSuffix() {
        ThreadedNode node = root;

        threadedListSuffix(root);
    }
    private void threadedListSuffix(ThreadedNode node){
        if(node == null){
            return;
        }
        /*
        * node.left != prePointer 依旧是防止环路
        *
        * */
        if(node.left != null && node.left != prePointer){
            prePointer = node;
            threadedListSuffix(((ThreadedNode)node.left));

        }
        System.out.println(node.item);
        /*
        *
        * 当节点的right指向的是右子树，就不能继续遍历了，否则会产生环路
        *   否则，会通过right子树跳转到之前已经遍历过的子节点，子节点再指向本父节点
        *   51->50->51
        * */
        if(node.rightPointerType != null) {
            prePointer = node;
            threadedListSuffix(((ThreadedNode) node.right));
        }

    }
    /**
     * 对二叉树进行后续线索化
     */
    public void threadedNodesSuffix() {
        threadedNodesSuffix(root);
    }

    private void threadedNodesSuffix(ThreadedNode temp) {
        if (temp == null) {
            return;
        }
        /*
         * 1.对左子树进行线索化
         * */
        threadedNodesSuffix(((ThreadedNode) temp.left));
        /*
         * 2.对右子树进行线索化
         * */
        threadedNodesSuffix(((ThreadedNode) temp.right));
        /*
         * 线索化当前节点
         * */
        if (temp.left == null) {
            temp.left = prePointer;
            temp.leftPointerType = LeftPointerType.precursorNode;
        }
        if (prePointer != null && prePointer.right == null) {
            prePointer.right = temp;
            prePointer.rightPointerType = RightPointerType.descendantNode;
        }
        prePointer = temp;

    }

    /**
     * 遍历前序线索化二叉树
     */
    public void threadedListPreOrder() {

        threadedListPreOrder(root);
    }

    private void threadedListPreOrder(ThreadedNode temp) {
        if (temp == null) {
            return;
        }
        System.out.println(temp.item);
        /*
         * temp.left != prePointer 防止在向左递归到达叶子节点
         *  但因为是前序线索化，即使是到达了叶子节点也依然能通过left找到父节点
         *   父节点又递归到本叶子节点，造成堆栈溢出错误
         *   和前序线索化的写法类似
         * */
        if (temp.left != null && temp.left != prePointer) {
            prePointer = temp;
            threadedListPreOrder(((ThreadedNode) temp.left));
            /*
             * 防止在线索化完成之后，之前已经遍历了的节点继续往下遍历
             *
             * */
            return;
        }
        if (temp.right != null) {
            prePointer = temp;
            threadedListPreOrder(((ThreadedNode) temp.right));
            return;
        }
    }

    public void threadNodesPreOrder() {
        threadedNodesPreOrder(root);
    }

    /**
     * 对二叉树进行前序线索化
     *
     * @param node
     */
    private void threadedNodesPreOrder(ThreadedNode node) {
        if (node == null) {
            return;
        }
        /*
         * 1.线索化当前节点
         * */

        if (node.left == null) {
            node.left = prePointer;
            node.leftPointerType = LeftPointerType.precursorNode;
        }
        if (prePointer != null && prePointer.right == null) {
            prePointer.right = node;
            prePointer.rightPointerType = RightPointerType.descendantNode;
        }
        prePointer = node;

        /*
         * 2.线索化左子树
         *      如果不加判断，在设置了前驱节点之后，会通过node.left跳转到设置的前驱节点
         *      形成闭环，直到堆栈溢出
         * */
        if (node.leftPointerType != LeftPointerType.precursorNode) {

            threadedNodesPreOrder((ThreadedNode) (node.left));
        }

        /*
         * 3.线索化右子树
         * */
        threadedNodesPreOrder((ThreadedNode) (node.right));
    }

    /**
     * 对中序线索化进行封装
     */
    public void threadedNodesInfix() {
        threadedNodesInfix(root);
    }

    /**
     * 对二叉树进行中序线索化
     * 线索化之后就不能用之前的前序、中序、后序 来遍历二叉树了
     * 因为之前遍历二叉树是递归到叶子节点（left、right指针都为null），才开始遍历的，
     * 而线索化之后，只有第一个节点的left、和最后一个节点的right指针为null
     * 其余叶子节点都指向了前驱节点或者后继节点
     * 普通遍历的时候可能会出现死循环
     *
     * @param node 当前需要线索化的节点
     */
    private void threadedNodesInfix(ThreadedNode node) {
        if (node == null) {
            return;
        }
        /*
         * 因为是中序遍历，所以先
         * 1.线索化左子树
         * */
        threadedNodesInfix((ThreadedNode) node.left);

        /*
         * 2.线索化当前节点
         *   (1)线索化当前节点的前驱节点
         *    不用设置  && node.prePointer != null  条件，中序遍历到的第一个节点前驱可以为null
         *      但依旧可以是前驱指针
         * */
        if (node.left == null) {
            /*
             * 让当前节点的左指针指向前驱节点
             * */
            node.left = prePointer;
            /*
             * 修改当前节点的指针类型，指向前驱节点
             * */
            node.leftPointerType = LeftPointerType.precursorNode;
        }
        /*
         * (2)线索化上一个节点的后继节点，
         *       非null判断，因为第一个 节点没有前一个节点，若第一个节点调用前一个节点的right指针，则NullPointerException
         *   本节点查找下一个节点比较困难，可以转环一下
         *       通过下一个节点的指针prePointer找到上一个节点，再设置上一个节点的后继节点指向本节点就简单多了
         * */
        if (prePointer != null && prePointer.right == null) {
//            让前驱节点的右指针指向当前节点，完成当前节点的前驱节点的后继节点的设置
            prePointer.right = node;
            /*
             * 修改当前节点的前驱节点的后继节点（右指针）的类型
             * */
            prePointer.rightPointerType = RightPointerType.descendantNode;
        }
        /*
         * 更新指针，每处理一个节点之后，让当前节点是下一个节点的前驱指针
         * */
        prePointer = node;

        /*
         * 3.线索化右子树
         * */
        threadedNodesInfix((ThreadedNode) node.right);
    }


    /**
     * 中序、前序、后序遍历二叉树只能在线索化之前遍历，线索化方法有说明为什么
     * <p>
     * 重写父类的前序遍历
     * <p>
     * 要遍历的节点对象已经不是原来的Node节点
     * 而是继承了Node类的ThreadedNode 线索化的节点
     */
    public void prefixList() {
        Node temp = root;
        //调用父类的前序遍历
        preOrder(temp, 0);
    }

    /**
     * 重写父类的中序遍历
     */
    public void infixList() {
        ThreadedNode temp = this.root;
        //调用父类的中序遍历
        infix(temp, 0);
    }

    /**
     * 重写父类的后序遍历
     */
    public void suffixList() {
        Node temp = root;
        //调用父类的后序遍历
        suffix(temp, 0);
    }

    /**
     * 必须把Node改为ThreadedNode 否则 left和right调用的就是ThreadedNode父类Node的left,right
     * 而ThreadedNode本身的left和right始终都为null
     * 之后线索化调用ThreadedNode时，left，right都为null，没有进行线索化，所以失败
     *
     * @param heroNode
     */
    public void addOrderly(HeroNode heroNode) {
        if (root == null) {
            root = new ThreadedNode(heroNode);
            return;
        }
        ThreadedNode temp = this.root;
        while (true) {
            if (heroNode.id > temp.item.id) {

                if (temp.right != null) {
                    /**
                     * 万万没想到，用强制类型转换
                     */
                    temp = (ThreadedNode) temp.right;
                } else {
                    temp.right = new ThreadedNode(heroNode);
                    return;
                }
            } else if (heroNode.id < temp.item.id) {

                if (temp.left != null) {
                    temp = (ThreadedNode) temp.left;
                } else {
                    temp.left = new ThreadedNode(heroNode);
                    return;
                }
            } else {
                System.err.println("节点ID已经存在");
                break;
            }

        }
    }


    /**
     * 这样简单遍历线索化二叉树只适用于中序二叉树
     */
    @Deprecated
    public void threadedListPreOrderOld() {
        /*
         * 找到线索化之后的第一个节点
         * 中序线索化之后，第一个节点的left指针为null，且LeftPointerType为precursorNode
         *      虽然前驱指针为null，但是它依然是一个前驱指针
         * */
        Node temp = root;
        if (temp == null) {
            System.out.println("该二叉树的根节点为null");
            return;
        }
        /*
         * 寻找第一个节点
         * */
        while (temp.left != null) {
            temp = temp.left;
        }
        /*
         * 开始遍历线索化二叉树
         * */
        while (temp != null) {
            System.out.println(((ThreadedNode) temp).toString());
            temp = temp.right;
        }
    }

    /**
     * 反向遍历线索化二叉树
     * 只适用于中序二叉树
     */
    @Deprecated
    public void reverseThreadedList() {
        Node temp = root;
        if (temp == null) {
            System.out.println("该线索化二叉树为null");
            return;
        }
        while (temp.right != null) {
            temp = temp.right;
        }
        while (temp != null) {
            System.out.println(((ThreadedNode) temp).toString());
            temp = temp.left;
        }
    }

    public ThreadedNode getRoot() {
        return root;
    }
}
